package algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class leetcode_0187 {
    public List<String> findRepeatedDnaSequences(String s) {
        int[] num = new int[s.length()];
        for(int i=0;i<s.length();++i){
            if(s.charAt(i)=='A'){
                num[i]=0;
            }else if(s.charAt(i)=='C'){
                num[i]=1;
            }else if(s.charAt(i)=='G'){
                num[i]=2;
            }else{
                num[i]=3;
            }
        }
        HashSet<Integer> set = new HashSet<>();
        List<String> result = new ArrayList<>();
        HashSet<String> resultSet = new HashSet<>();
        int left = 0;
        int right = 0;
        int len=0;
        int current=0;
        while(right<s.length()){
            current = current*4 +num[right];
            right++;
            len++;
            if(len>10){
                current = current - (int) Math.pow(4,len-1)*num[left];
                len--;
                left++;
            }
            if(len==10){
                if(set.contains(current)){
                    resultSet.add(s.substring(left,right));
                }else{
                    set.add(current);
                }
            }
        }
        for(String tmp:resultSet){
            result.add(tmp);
        }
        return result;
    }
}
